/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

/**
 * <p>
 * 移除倒数的第n个节点
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月21日
 */
public class RemoveNthNodeFromEndofList {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        if (n < 0 || head == null) {
            return head;
        }
        dummy.next = head;
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < n-1; i++) {
            if (second.next == null) {
                return head;
            } else {
                second = second.next;
            }
        }
//        System.out.println(first.val+"\t"+second.val);
        ListNode pre = dummy;
        while (second.next != null) {
            second = second.next;
            pre = first;
            first = first.next;
        }
        // 移除第first个元素
        pre.next = first.next;

        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(3);
        node.next.next.next = new ListNode(4);
        node.next.next.next.next = new ListNode(5);
        node.next.next.next.next.next = new ListNode(6);
        RemoveNthNodeFromEndofList remover = new RemoveNthNodeFromEndofList();
        ListNode root = remover.removeNthFromEnd(node, 6);//删除4
        ListNode curNode = root;
        while(curNode!=null){
         System.out.println(curNode.val);
         curNode = curNode.next;
        }
    }
}
